/*
有且仅有一个假币，不知假币是重是轻，求假币序号
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int no;		// 找到的假币编号 
int light;	// 假币比真币轻（1）或者重（-1）
int cnt;	// 称重总次数 

// c[ia]和c[ib]开始的n个硬币称重一次 
int Balance(vector<int>&c, int ia, int ib, int n)
{
	// 称重一次 
	cnt++;
	
	// 统计重量
	int sa=0, sb=0;
	for(int i=ia,j=0;j<n;i++,j++)
		sa+=c[i];
	for(int i=ib,j=0;j<n;i++,j++)
		sb+=c[i];
	
	// A轻 
	if(sa<sb)
		return 1;
	
	// A，B重量相同 
	else if(sa==sb)
		return 0;
	
	// B轻
	else
		return -1;
}

// 在coins[i..i+n-1](共n个硬币)中查找假币
void spcoin(vector<int> &coins, int i, int n)
{
	// 剩余1个硬币coins[i] 
	if(n==1)
		no=i;
	
	// 剩余2个硬币coins[i]和coins[i+1]
	else if(n == 2)
	{
		// 2个硬币称重
		int b = Balance(coins, i, i+1, 1);
		
		// coins[i]是假币
		if(b == light)
			no=i;
		
		// coins[i+1]是假币
		else
			no=i+1;
	}
	
	// 剩余3个或者以上硬币coins[i..i+n-1]
	else
	{
		// k为A和B中的硬币个数
		int k;
		if(n%3==0 || n%3==1)
			k = n/3;
		else
			k = n/3+1;
		
		// 分为A,B,C,硬币个数分别为k,k,n-2k
		int ia=i,ib=i+k,ic=i+2*k;
		
		// A,B称重一次
		int b = Balance(coins,ia,ib,k);
		
		// A,B的重量相同，假币在C中
		if(b == 0)
			spcoin(coins, ic, n-2*k); // 在C中查找假币
		
		// 假币A中
		else if(b == light)
			spcoin(coins, ia, k); // 在A中查找假币
		
		// 假币在B中，在B中查找假币
		else spcoin(coins, ib, k);
	}
}

int main() 
{
	// 9个硬币
	int n = 9;
	
	// 存放所有的硬币
	vector<int> c(n, 2);
	
	// 指定编号i为假币
	c[2]=1;
	
	// no为假币序号，light为轻重标记
	no=-1; light=1;
	
	// 查找假币
	printf("求解结果\n");
	spcoin(c, 0, n);
	
	// 打印结果
	printf("    假币为%d, 假币%s\n", no, (light==1?"轻":"重"));
	return 0;
}
	

